package org.benetech.util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.benetech.beans.Filter;
import org.benetech.beans.RelativeText;
import org.benetech.collections.ListMap;
import org.benetech.collections.Tree;
import org.benetech.collections.Tree.ListDirection;
import org.benetech.ref.XML;
import org.jdom.Attribute;
import org.jdom.Content;
import org.jdom.Document;
import org.jdom.Element;
import org.jdom.Text;

/**
 * Utilities to help make observations about an XML document, or elements in that document.
 * @author Reuben Firmin
 */
public final class XMLParseUtils {

	/**
	 * Non-constructor.
	 */
	private XMLParseUtils() {
		// empty
	}

	/**
     * Return the children of the given element as a map of name -> element. This is useful to circumvent the necessity
     * to specify a namespace on Element#getChild.
     *
     * @param element never null
     * @return never null
     */
    public static ListMap<String, Element> getChildrenAsMap(final Element element) {
    	final ListMap<String, Element> childMap = new ListMap<String, Element>();
    	final Iterator<Element> children = (Iterator<Element>) element.getChildren().iterator();
    	while (children.hasNext()) {
    		final Element child = children.next();
    		childMap.put(child.getName(), child);
    	}
    	return childMap;
    }

	/**
     * Gets all descendents of a given element as a map of element name -> elements with that name.
     *
     * @param element never null
     * @return never null
     */
    public static ListMap<String, Element> getDescendentsAsMap(final Element element) {
    	final ListMap<String, Element> descendentMap = new ListMap<String, Element>();
    	final Iterator descendents = element.getDescendants();
    	while (descendents.hasNext()) {
    		final Object o = descendents.next();
    		if (o instanceof Element) {
    			final Element desc = (Element) o;
    			descendentMap.put(desc.getName(), desc);
    		}
    	}
    	return descendentMap;
    }

	/**
     * Get the total elements of a given element name within the document.
     *
     * @param document The document
     * @param elementName The name of the elements to count
     * @return Never null
     */
    public static Integer getTotalElements(final Document document, final String elementName) {
    	final List<Document> documents = new ArrayList<Document>();
    	documents.add(document);
    	return XMLParseUtils.getTotalElements(documents, elementName);
    }

	/**
     * Get the total elements of the given name within the supplied list of documents.
     *
     * @param documents The list of documents.
     * @param elementName The name of the elements to count.
     * @return A number, never null.
     */
    public static Integer getTotalElements(final List<Document> documents, final String elementName) {
    	int count = 0;
    	for (Document document : documents) {
    		final Iterator iterator = document.getRootElement().getDescendants(new org.jdom.filter.Filter() {
    			public boolean matches(final Object obj) {
    				return obj instanceof Element && elementName.equals(((Element) obj).getName());
    			}
    		});
    		while (iterator.hasNext()) {
    			count++;
    			iterator.next();
    		}
    	}
    	return count;
    }

	/**
     * Get indices of elements in this list which pass the filter.
     *
     * @param elements The list of elements
     * @param filter The filter to run across the list
     * @return never null
     */
    public static List<Integer> getMatchingIndices(final List<Element> elements, final Filter<Element, ? > filter) {
    	final List<Integer> indices = new ArrayList<Integer>();
    	for (int i = 0; i < elements.size(); i++) {
    		final Element el = elements.get(i);
    		if (filter.accept(el)) {
    			indices.add(i);
    		}
    	}
    	return indices;
    }

	/**
     * Find elements descending from this element which match one or more of the filters.
     * If the filters are null, return all descendents.
     *
     * @param element The element whose descendents to search
     * @param filters One or more filters that determine which elements to return; null for all
     * @return List containing all matching elements
     * @see #getElementAsTree(Element, Filter), {@link XMLTreeUtils#getDocumentAsTree(Document, Filter)}
     */
    public static List<Element> find(final Element element, final Filter<Element, ? >... filters) {
    	final Iterator<Element> iterator = (Iterator<Element>) element.getDescendants();
    	final List<Element> acceptedChildren = new ArrayList<Element>();
    	while (iterator.hasNext()) {
    		final Object child = iterator.next();
    		if (child instanceof Element) {
    			if (filters == null || filters.length == 0) {
    				acceptedChildren.add((Element) child);
    			} else {
    				for (Filter<Element, ? > filter : filters) {
    					if (filter.accept((Element) child)) {
    						acceptedChildren.add((Element) child);
    						break;
    					}
    				}
    			}

    		}
    	}
    	return acceptedChildren;
    }

	/**
     * Return the string nearest to this element, either forward or back. Return the name of it's id attribute as a fall
     * back, or null if nothing else works.
     *
     * @param element The element to find the text nearest to
     * @param tree The tree of the document
     * @param direction Null if either direction if ok, true to force forward search, false to force backward search
     * @return null if the bounds of the tree were hit without finding text, and the element doesn't have an id element.
     */
    public static RelativeText getNearestText(final Element element, final Tree<Element, ?, ?> tree,
    		final Boolean direction, final Pattern... exceptElementsMatching)
    {
    	final List<Element> contentList = tree.toContentList(ListDirection.DEPTH);
    	if (element.getTextNormalize().length() == 0) {
    		int i = 0;
    		// find the index of the element
    		for (; i < contentList.size() && !contentList.get(i).equals(element); i++) {
    			// no-op
    		}
    		for (int j = 0; j + i < contentList.size(); j++) {
    			if (direction == null || direction) {
    				final Element e = contentList.get(j + i);
    				elementConsiderable : {
	    				for (Pattern pattern : exceptElementsMatching) {
	    					if (pattern.matcher(e.getName()).matches()) {
	    						break elementConsiderable;
	    					}
	    				}
	    				final String fwd = e.getTextNormalize();
	    				if (fwd.length() > 0) {
	    					return new RelativeText(true, j, fwd);
	    				}
    				}
    			}

    			if ((direction == null || !direction) && (i - j > 0)) {
    				final Element e = contentList.get(i - j);
    				elementConsiderable : {
	    				for (Pattern pattern : exceptElementsMatching) {
	    					if (pattern.matcher(e.getName()).matches()) {
	    						break elementConsiderable;
	    					}
	    				}
	    				final String back = e.getTextNormalize();
	    				if (back.length() > 0) {
	    					return new RelativeText(true, j, back);
	    				}
    				}
    			}
    		}
    		return null;
    	} else {
    		return new RelativeText(true, 0, element.getTextNormalize());
    	}
    }


    /**
     * Return the Element of the string nearest to this element, either forward or back.
     *
     * @param element The element to find the text nearest to
     * @param tree The tree of the document
     * @param direction Null if either direction if ok, true to force forward search, false to force backward search
     * @return null if the bounds of the tree or the stopElemName were hit without finding text, and the element doesn't have an id element.
     */

    final static String PAGENUM = "pagenum";
    public static Element getNearestTextElement(final Element element, Element doc,
    		String stopElemName, final Boolean direction)
    {
    	final List<Element> contentList = XMLParseUtils.flattenToList(doc);
    	boolean doneDown = false;
    	boolean doneUp = false;
    	if (direction != null) {
    		 if (direction) {
    			 doneUp = true;
    		 } else {
    			 doneDown = true;
    		 }
    	}
    	int i = 0;
    	// find the index of the element
    	for (; i < contentList.size() && !contentList.get(i).equals(element); i++) {
    		// no-op
    	}
    	for (int j = 1; !doneDown || !doneUp ; j++) {
    		if (!doneDown) {
    			final Element elem = (i + j < contentList.size()) ? contentList.get(i + j) : null;
    			if (elem == null || elem.getName().equals(stopElemName)){ doneDown = true; };
    			if (!doneDown && !elem.getName().equals(PAGENUM)) {
    				final String fwd = elem.getTextNormalize();
    				if (fwd.length() > 0) {
    					return contentList.get(j + i);
    				}
    			}
    		}
    		if (!doneUp) {
    			final Element elem = (i - j >= 0) ? contentList.get(i - j) : null;
    			if (elem == null || elem.getName().equals(stopElemName)) { doneUp = true; }
    			if (!doneUp && !elem.getName().equals(PAGENUM)) {
    				final String back = elem.getTextNormalize();
    				if (back.length() > 0) {
    					return contentList.get(i - j);
    				}
    			}
    		}
    	}
    	return null;
    }


	/**
     * Return the node of nearest number to this element, either forward or back.
     *
     * @param element The element to find the text nearest to
     * @param tree The tree of the document
     * @param direction Null if either direction if ok, true to force forward search, false to force backward search
     * @return null if the bounds of the tree or pagenum were hit without finding text, and the element doesn't have an id element.
     */
    public static Element getNearestNumber(final Element element,
	        final Element rootElem, String stopElemName, final Boolean direction)
    {
		final List<Element> contentList = flattenToList(rootElem);

		Matcher matcher = (XML.Regex.NUMBER_PATTERN).matcher(element.getTextNormalize());
		if (matcher.matches()) {
			return element;
		}

		boolean doneDown = false;
    	boolean doneUp = false;
    	if (direction != null) {
    		if (direction) {
    			doneUp = true;
    		} else {
    			doneDown = true;
    		}
    	}

		 int i = 0;
		// find the index of the element
		 for (; i < contentList.size() && !contentList.get(i).equals(element); i++) {
		// no-op
		 }
    	for (int j = 1; !doneDown || !doneUp ; j++) {
    		if (!doneDown) {
    			final Element elem = (i + j < contentList.size()) ? contentList.get(i + j) : null;
    			if (elem == null || elem.getName().equals(stopElemName)){ doneDown = true; };
    			if (!doneDown) {
					matcher = (XML.Regex.NUMBER_PATTERN).matcher(elem.getTextNormalize());
					if (matcher.matches()) {
						return contentList.get(j + i);
					}
				}
			}
    		if (!doneUp) {
				final Element elem = (i - j >= 0) ? contentList.get(i - j) : null;
				if (elem == null || elem.getName().equals(stopElemName)) { doneUp = true; }
				if (!doneUp) {
					matcher = (XML.Regex.NUMBER_PATTERN).matcher(elem.getTextNormalize());
					if (matcher != null && matcher.matches()) {
						return contentList.get(i - j);
					}
				}
			}
		}
		return null;
	}

	/**
	 * Return the position that this element is in, relative to its parent. If it is the first child, 0 will be returned
	 *
	 * @param e The element
	 * @return Null if there is no parent, index otherwise
	 */
    public static Integer childPosition(final Element e) {
    	if (e.getParent() == null) {
    		return null;
    	}

    	final List<Element> siblings = e.getParentElement().getChildren();
    	for (int i = 0; i < siblings.size(); i++) {
    		if (e.equals(siblings.get(i))) {
    			return i;
    		}
    	}
    	throw new RuntimeException("Logical problem - element must exist in its parents children");
    }

    /**
     * @see #childPosition(Element)
     * @param e Never null
     * @return Never null
     */
    public static Integer indexOf(final Element e) {
    	return childPosition(e);
    }

    /**
     * Returns the adjacent content of the given element.
     * @param e given element
     * @param direction direction to look
     * @return null if no adjacentContent
     */
    public static Content getAdjacentContent(final Element e, final boolean direction) {
    	final Element parent = e.getParentElement();
    	if (parent == null) {
    		return null;
    	}
    	final Content[] parentContent = (Content[]) parent.getContent().toArray(new Content[0]);
    	int i = 0;
    	// find the secondary
    	for (; i < parentContent.length && !parentContent[i].equals(e);	i++)
    	{ // do nothing
    	}
    	if (direction) {
    		if (++i < parentContent.length) {
    			return parentContent[i];
    		}
    		return null;
    	} else {
    		if (--i >= 0) {
    			return parentContent[i];
    		}
    	}
    	return null;
    }
    /**
     * Test these two elements to see if they are adjacent. That is, they have the same parent, and are next to each
     * other. Order is unimportant.
     * @param e1 The first element
     * @param e2 The second element
     * @return True if they are adjacent; if either has a null parent, false
     */
    public static boolean adjacent(final Element e1, final Element e2) {
    	if (e1.getParent() == null || e2.getParent() == null) {
    		return false;
    	}
    	if (!e1.getParent().equals(e2.getParent())) {
    		return false;
    	}
    	final List<Element> siblings = e1.getParentElement().getChildren();
    	for (int i = 0; i < siblings.size(); i++) {
    		final Element element = siblings.get(i);
    		if (element.equals(e1)) {
    			return ((i > 0 && siblings.get(i - 1).equals(e2))
    					|| (i + 1 < siblings.size() && siblings.get(i + 1).equals(e2)));
    		}
    	}
    	return false;
    }

	/**
     * Get a map of attribute name -> attribute, based on an element's attributes.
     *
     * @param element The element whose attributes to retrieve.
     * @return Never null
     */
    public static Map<String, Attribute> getAttributeMap(final Element element) {
    	final List<Attribute> attributes = (List<Attribute>) element.getAttributes();
    	final Map<String, Attribute> attributeMap = new HashMap<String, Attribute>();
    	for (Attribute attribute : attributes) {
    		attributeMap.put(attribute.getName(), attribute);
    	}
    	return attributeMap;
    }

	/**
     * Extract the text from this XML. Spaces are inserted between text pulled from different elements. There is no
     * concern for layout.
     *
     * @param rootElement The element to extract text from
     * @return Never null
     */
    public static String extractText(final Element rootElement) {
    	return extractText(rootElement, false);
    	/*final StringBuffer buffer = new StringBuffer();
    	boolean appending = false;
    	for (Element element : flattenToList(rootElement)) {
    		final String text = element.getTextNormalize();
    		if (text.length() > 0) {
    			if (appending) {
    				buffer.append(" ");
    			}
    			buffer.append(text);
    			appending = true;
    		}
    	}
    	return buffer.toString();
    	*/
    }


	/**
     * Extract the text from this XML. Spaces are inserted between text pulled from different elements. There is no
     * concern for layout.
     *
     * @param rootElement The element to extract text from
     * @return Never null
     */
    public static String extractText(final Element rootElement, boolean appending) {
    	final StringBuffer buffer = new StringBuffer();
    	final Content[] content = (Content[]) rootElement.getContent().toArray(new Content[0]);
		boolean append = appending;
    	for (int i = 0; i < content.length; i++) {
			if (content[i] instanceof Text) {
				if (append) {
    				buffer.append(" ");
    			}
				final String text = ((Text) content[i]).getTextNormalize();
	    		buffer.append(text);
	    		append = true;
			} else if (content[i] instanceof Element) {
	    		final String text = extractText((Element) content[i], true);
	    		buffer.append(text);
	    		append = true;
			}
		}
    	return buffer.toString();
    }


    /**
     * Extracts text from this document.
     * @param document The document to extract text from
     * @return Never null
     */
    public static String extractText(final Document document) {
    	return extractText(document.getRootElement());
    }

	/**
     * Flatten an XML document to a list on a depth-first basis; the first element is the root.
     *
     * @param rootElement never null
     * @return List of elements, never null
     */
    public static List<Element> flattenToList(final Element rootElement) {
    	final List<Element> elements = new ArrayList<Element>();
    	elements.add(rootElement);
    	final Iterator iterator = rootElement.getDescendants();
    	while (iterator.hasNext()) {
    		final Object o = iterator.next();
    		if (o instanceof Element) {
    			elements.add((Element) o);
    		}
    	}
    	return elements;
    }

	/**
     * Flatten an XML document to a list on a depth-first basis; the first element is the root.
     *
     * @param document never null
     * @return List of elements, never null
     */
    public static List<Element> flattenToList(final Document document) {
    	return flattenToList(document.getRootElement());
    }

    /**
     * Given a map of possibleElement -> relativeElement, identify the possible elements that are most similar. This
     * is a combination of  "path from relative element" and attributes of the element itself.
     * @param elements the possibleElement to relativeElement map
     * @return a list of the mostSimilar Elements
     */
    final static int ATTRIBUTE_WEIGHT = 10;
    final static int NAME_WEIGHT = 1;
    public static List<Element> getMostSimilar(final Map<Element, Element> elements) {
    	final Map<Element, Integer> scores = new HashMap<Element, Integer>();
    	final Map<Element, Integer> indices = getIndices(new MapUtils<Element, Element>().getAsList(elements));
    	// score each on distance from pair
    	for (Map.Entry<Element, Element> elementPair : elements.entrySet()) {
    		final Integer index1 = indices.get(elementPair.getKey());
    		final Integer index2 = indices.get(elementPair.getValue());
    		if (index1 == null || index2 == null) {
    			// XXX
    			throw new RuntimeException("Element is not in the same document");
    		}
    		// TODO this needs to be weighted (experiment w/ different weightings)
    		scores.put(elementPair.getKey(), new Integer(Math.abs(index1 - index2)));
    		// score the structure of the path between them...
    		// TODO
    	}

    	for (Element elem : elements.keySet()) {
    		int score = scores.get(elem);
    		final List<Attribute> elemAttributes = elem.getAttributes();
    		final String elemString = elem.getTextNormalize();
    		for (Element elemCompare : elements.keySet()) {
    			final String cur = elemCompare.getTextNormalize();
    			score += StringUtils.levenshteinDistance(elemString, cur);
    			if (!elem.getName().equals(elemCompare.getName())){
    				score += NAME_WEIGHT;
    			}
    			for (Attribute cont : elemAttributes){
    				if (null == elemCompare.getAttribute(cont.getName())){
    					score += ATTRIBUTE_WEIGHT;
    				}
    			}

        	}
    		scores.put(elem, score);
    	}
    	// score each attribute; also needs to be weighted (again experiment w/ different weightings)
    	// TODO

    	// now find the most similar. this is the group who's difference from the average score is less or equal
    	// than the average distance from the average score
    	int total = 0;
    	int size = scores.values().size();
    	for (Integer score : scores.values()) {
    		total += score;
    	}
    	int average = Math.round((float)total / size);
    	int totalDistance = 0;
    	for (Integer score : scores.values()) {
    		totalDistance += Math.abs(score - average);
    	}
    	int avgDistance = Math.round((float)totalDistance / size);
    	final List<Element> mostSimilar = new ArrayList<Element>();
    	for (Map.Entry<Element, Integer> scoredElement : scores.entrySet()) {
    		if (scoredElement.getValue() <= 20 * size && scoredElement.getValue() <= (average + avgDistance)) {
    			mostSimilar.add(scoredElement.getKey());
    		}
    	}
    	return mostSimilar;
    }

    /**
     * Get the indices of these elements, relative to the head of the tree. All elements must be part of the same
     * document (if not, elements which are not part of the same document as the first element in the group will not
     * be returned with indices.) The map will be ordered by index.
     * @param elements The elements to find indices for
     * @return Never null
     */
    public static Map<Element, Integer> getIndices(List<Element> elements) {
    	final Map<Element, Integer> indices = new LinkedHashMap<Element, Integer>();
    	if (elements.size() > 0) {
    		final Element first = elements.get(0);
    		final List<Element> documentList = flattenToList(getRoot(first));
    		for (int i = 0; i < documentList.size(); i++) {
    			Element element = documentList.get(i);
    			if (elements.contains(element)) {
    				indices.put(element, i);
    			}
    		}
    	}
    	return indices;
    }

    /**
     * Gets the root element of the document that this element is in.
     * @param element Not null
     * @return The root element
     */
    public static Element getRoot(final Element element) {
    	Element current = element;
    	Element parent = element.getParentElement();
    	while (parent != null) {
    		current = parent;
    		parent = current.getParentElement();
    	}
    	return current;
    }

    /**
     * Recursive method to determine whether an element accepted by the filter exists under the given element.
     * @param element The element whose descendents to look through
     * @param filter Filter whose acceptance determines the result of this method
     * @return Never null
     */
    public static boolean existsUnder(final Element element, final Filter<Element, ?> filter) {
    	for (Element child : (List<Element>) element.getChildren()) {
    		if (filter.accept(child)) {
    			return true;
    		}
    		if (existsUnder(child, filter)) {
    			return true;
    		}
    	}
    	return false;
    }

    /**
     * Return true if siblings of this element, either before or after it, pass all of the given filters. Note, will
     * return false if the element is not found. If there are no siblings in the given direction, it will return true;
     * this can be tested for by using {@link #childPosition(Element)}
     * @param element The element whose siblings to look at
     * @param before True to look at siblings that come before this element
     * @param filters The filters to run against the siblings
     * @return True or false
     */
    public static boolean siblingsMatch(final Element element, final boolean before,
    	final Filter<Element, ? >... filters)
    {
    	if (element.getParent() == null) {
    		return false;
    	}

    	final List<Element> siblings = element.getParentElement().getChildren();
    	boolean found = false;
    	for (int i = 0; i < siblings.size(); i++) {
    		boolean thisIsTheElement = false;
    		if (element.equals(siblings.get(i))) {
    			found = true;
    			thisIsTheElement = true;
    		}
    		if (!found && before || found && !before && !thisIsTheElement) {
    			for (Filter<Element, ? > filter : filters) {
    				if (!filter.accept(siblings.get(i))) {
    					return false;
    				}
    			}
    		}
    	}
    	return found;
    }

    /**
     * Expensive operation. Calculate the index of this element, relevant to its document.
     * @param el Must be in a document
     * @return
     */
    public static int documentIndex(Element el) {
    	return XMLTreeUtils.getDocumentAsTree(el.getDocument(), null).toList(ListDirection.DEPTH).indexOf(el);
    }

	/**
	 * Search the ancestors (parent, grandparent, great-grandparent, etc) of the specified
	 * Element to see if any match a terminator pattern.  If no match is found, then return
	 * the root Element of the document.
	 *
	 * @param child The starting point of the search (may not be null)
	 * @param terminators Element name(s) to act as a boundary (may not be null)
	 * @return The ancestor (or document root) Element.
	 */
	public static Element findAncestor(final Element child, final Pattern... terminators) {
		Element ancestor = null;
		Element parent   = child.getParentElement();
	
		while ((parent != null) && (ancestor == null)) {
	
			for (Pattern pattern : terminators) {
				final Matcher matcher = pattern.matcher(parent.getName());
				if (matcher.matches()) {
					ancestor = parent;
				}
			}
	
			//Only continue the loop if no match was found
			if (ancestor == null) {
				parent = parent.getParentElement();
			}
		}
	
		return ancestor;
	}

	/**
	 * Search the older siblings of a child Element to find a match to the terminator
	 * pattern.  If multiple matches are found, the match closest to the child Element
	 * is returned.
	 *
	 * @param child The child Element to be used as the boundary of the search.
	 * @param terminators  Element name(s) to act as a boundary
	 * @return If a match is found, a reference to that Element is returned.  If no
	 * match is found, null is returned.
	 */
	public static Element findSiblingBeforeChild(final Element child, final Pattern... terminators) {
	
		final Element[] children = (Element[]) child.getParentElement().getChildren().toArray(new Element[0]);
		Element sibling = null;
	
		for (int i = 0; i < children.length; i++) {
			final Element next = children[i];
	
			if (next.equals(child)) {
				break;
			}
	
			for (Pattern pattern : terminators) {
				final Matcher matcher = pattern.matcher(next.getName());
				if (matcher.matches()) {
					sibling = next;
				}
			}
		}
	
		return sibling;
	}
}
